package thired.class13_monotonousstack;

import java.util.Stack;

public class Class04_MaximalRectangle {
    public int maximalRectangle(char[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }
        int maxArea = 0;
        int[] height = new int[map[0].length];
        for (int i = 0; i < map.length; i++) {

            for (int j = 0; j < map[i].length; j++) {
                height[j] = map[i][j] == 1 ? height[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea,(maxRecFromBottom(height)));

        }
        return maxArea;
    }

    public static int maxRecFromBottom(int[] height){
        if (height == null || height.length == 0) {
            return 0;
        }
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]){
                int cur = stack.pop();
                maxArea = Math.max(maxArea, height[cur] * (stack.isEmpty() ? i : i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int cur = stack.pop();
            maxArea = Math.max(maxArea, height[cur] * (stack.isEmpty() ? height.length : height.length - stack.peek() - 1));
        }
        return maxArea;
    }
}
